# 滑动窗口
# leetcode 76：
def minWindow(s: str, t: str) -> str:
    need, window = {}, {}
    for i in t:
        need[i] = need.get(i, 0) + 1

    left, right = 0, 0
    valid = 0
    start, lenth = 0, float('inf')
    # 左闭右开
    while right < len(s):
        # 右边加入的字符
        c = s[right]
        right += 1
        # 进行加入数据相关操作，先加入后判断操作
        if c in need:
            window[c] = window.get(c, 0) + 1
            if window[c] == need[c]:
                valid += 1
        # 满足条件时缩小窗口，进行最优寻找
        while valid == len(need):
            # 满足条件时更新答案
            if right - left < lenth:
                start = left
                lenth = right - left
            # 左边要取出的字符
            d = s[left]
            left += 1
            # 对数据进行去除操作，基本与添加操作顺序相反，先判断后删除
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1
    return '' if lenth == float('inf') else ''.join(s[start: start + lenth])


# leetcode3 最长无重复字串
def lengthOfLongestSubstring(s: str) -> int:
    left, right = 0, 0
    res = 0
    window = {}
    while right < len(s):
        c = s[right]
        right += 1
        window[c] = window.get(c, 0) + 1
        while window[c] > 1:
            d = s[left]
            left += 1
            window[d] -= 1
        res = max(res, right - left)
    return res


# leetcode438
def findAnagrams(s: str, p: str):
    if len(p) > len(s):
        return []
    res = []
    left, right = 0, 0
    window = {}
    need = {}
    for i in p:
        need[i] = need.get(i, 0) + 1
    valid = 0
    while right < len(s):
        c = s[right]
        right += 1
        if c in need:
            window[c] = window.get(c, 0) + 1
            if window[c] == need[c]:
                valid += 1
                if valid == len(need):
                    res.append(left)
        # print(window)
        while right - left + 1 > len(p):
            d = s[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1

    return res


# leetcode 567  字串问题注意区间，左闭右开
def checkInclusion(s1: str, s2: str) -> bool:
    if len(s2) < len(s1):
        return False
    window, need = {}, {}
    for i in s1:
        need[i] = need.get(i, 0) + 1
    left, right = 0, 0
    valid = 0
    while right < len(s2):
        c = s2[right]
        # 这里虽然right+1了，但是判断时是对上面c进行的所以右区间是开的[left， right, 这也就能解释后面直接判断结果时字符串长度问题
        right += 1
        if c in need:
            window[c] = window.get(c, 0) + 1
            if window[c] == need[c]:
                valid += 1
                if valid == len(need):
                    return True
        # 这里特别需要注意，这里会维持window比待对比字符串长度小一：（right - 1）- left + 1 是window内长度 等于s1就消除左边一个
        while right - left + 1 > len(s1):
            d = s2[left]
            left += 1
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1

    return False


if __name__ == '__main__':
    print(minWindow("ADOBECODEBANC", "ABC"))
    print(lengthOfLongestSubstring("abcabcbb"))
    print(findAnagrams("cbaebabacd", "abc"))
    print(checkInclusion("hello", "ooolleoooleh"))